Search for: All records

Time has become an essential aspect of many computing systems where temporal correctness is as important as functional correctness. Autonomous vehicles, Industry 4.0, and smart grids are a few examples of time-sensitive systems. As time-sensitive applications become large, complex, and distributed, traditional methods fall short of achieving the desired orchestration among components. In this vision article, we first propose a standard to maintain an accurate notion of time among all components of the system, i.e., sensors, computing platforms, and actuators. Then, we propose explicit-time state estimation and closed-loop control algorithms that can tolerate large delays while achieving reasonable performance, and an integrated fail-safe mechanism that achieves a high level of robustness when timing failures happen. 

Careful placement of a distributed computational application within a target device cluster is critical for achieving low application completion time. The problem is challenging due to its NP-hardness and combinatorial nature. In recent years, learning-based approaches have been proposed to learn a placement policy that can be applied to unseen applications, motivated by the problem of placing a neural network across cloud servers. These approaches, however, generally assume the device cluster is fixed, which is not the case in mobile or edge computing settings, where heterogeneous devices move in and out of range for a particular application. To address the challenge of scaling to different-sized device clusters and adapting to the addition of new devices, we propose a new learning approach called GiPH, which learns policies that generalize to dynamic device clusters via 1) a novel graph representation gpNet that efficiently encodes the information needed for choosing a good placement, and 2) a scalable graph neural network (GNN) that learns a summary of the gpNet information. GiPH turns the placement problem into that of finding a sequence of placement improvements, learning a policy for selecting this sequence that scales to problems of arbitrary size. We evaluate GiPH with a wide range of task graphs and device clusters and show that our learned policy rapidly finds good placements for new problem instances. GiPH finds placements that achieve up to 30.5% better makespan, searching up to 3× faster than other search-based placement policies. 

Many Cyber-Physical Systems (CPS) have timing constraints that must be met by the cyber components (software and the network) to ensure safety. It is a tedious job to check if a CPS meets its timing requirement especially when they are distributed and the software and/or the underlying computing platforms are complex. Furthermore, the system design is brittle since a timing failure can still happen e.g., network failure, soft error bit flip, etc. In this paper, we propose a new design methodology called Plan B where timing constraints of the CPS are monitored at the runtime, and a proper backup routine is executed when a timing failure happens to ensure safety. We provide a model on how to express the desired timing behavior using a set of timing constructs in a C/C++ code and how to efficiently monitor them at the runtime. We showcase the effectiveness of our approach by conducting experiments on three case studies: 1) the full software stack for autonomous driving (Apollo), 2) a multi-agent system with 1/10th scale model robots, and 3) a quadrotor for search and rescue application. We show that the system remains safe and stable even when intentional faults are injected to cause a timing failure. We also demonstrate that the system can achieve graceful degradation when a less extreme timing failure happens. 

Low-Power Wide-Area Networks (LP-WANs) are seeing wide-spread deployments connecting millions of sensors, each powered by a ten-year AA battery to radio infrastructure, often miles away. By design, iteratively querying all sensors in an LP-WAN may take several hours or even days, given the stringent battery limits of client radios. This precludes obtaining even an approximate real-time view of sensed information across LP-WAN devices over a large area, say in the event of a disaster, fault or simply for diagnostics.This paper presents QuAiL 1 , a system that provides a coarse aggregate view of sensed data across LP-WAN devices over a wide- area within a time span of just one LP-WAN packet. QuAiL achieves this by coordinating multiple LP-WAN radios to transmit their information synchronously in time and frequency despite their power constraints. We design each client's transmission so that the base station can retrieve an approximate heatmap of sensed data by exploiting the spatial correlation of this data across clients. We further show how our system can be optimized for statistical and machine learning queries, all while maintaining the security and privacy of sensed data from individual clients. Our deployment over a 3 sq. km. LP-WAN deployment around CMU campus in Pittsburgh demonstrates a 4x faster information retrieval versus the state-of- the-art statistical methods to retrieve the spatial sensor heatmap at a desired resolution. 

Low-Power Wide Area Networks, such as LoRaWAN, are rapidly gaining popularity in the field of wireless sensing and actuation. While LoRaWan is heavily studied in applications and performance, the concept of time has rarely been characterized in such networks. Many applications will require synchronized local clocks with varying levels of precision in order to maintain consistency and coordination in the network. Traditional time synchronization protocols however do not fit LoRaWAN's delay-inherent, low duty cycle, network model and wide-area deployment topology. Meanwhile, relying on GPS for time is not an option for low-power applications. In this paper, we present LongShoT, a time synchronization scheme built on LoRaWan capable of synchronizing device clocks to within 10μs of a reference clock with a single network request. This is achieved by utilizing the deterministic properties of Lo-Ra Wan networks along with hardware- and MAC-level timestamping of packets. LongShoT was implemented on consumer off-the-shelf hardware and evaluated over physically distributed devices using GPS 1PPS as a reference. Our results show that LongShoT achieves an average synchronization error of less than 2μs and compensates oscillator drift to less than 0.1ppm with devices distributed within 4km of a gateway.